package com.github.hgkmail.hello.leetcode101.firstsearch;

import java.util.*;

public class LC79WordSearch {
    //辅函数
    public void backtrack(char[][] board, char[] chars, boolean[][] visited, int level, List<Boolean> find, int i, int j) {
        //边界判定
        if (i<0 || i>=board.length || j<0 || j>=board[0].length || visited[i][j] || board[i][j]!=chars[level]) {
            return;
        }
        //已经找到了
        if (!find.isEmpty()) {
            return;
        }
        level+=1;
        visited[i][j]=true;
        //字符够了
        if (level>=chars.length) {
            find.add(Boolean.TRUE);
            return;
        }
        //字符不够，继续查找
        int x,y;
        int[] directions=new int[]{-1,0,1,0,-1};
        for (int k = 0; k < 4; k++) {
            x=i+directions[k];
            y=j+directions[k+1];
            backtrack(board, chars, visited, level, find, x, y);
        }
        //恢复
        //由于辅函数外部有循环，因此末尾要进行修改恢复！
        visited[i][j]=false;
        level-=1;
    }

    public boolean exist(char[][] board, String word) {
        //base case
        if (word.length()<=0) {
            return true;
        }
        if (board.length<=0 || board[0].length<=0) {
            return false;
        }
        char[] chars = word.toCharArray();
        //全局状态变量
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                visited[i][j]=false;
            }
        }
        //find: 是否找到
        //Java基础类型(String Boolean等)按引用传递——利用List
        List<Boolean> find = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                backtrack(board, chars, visited, 0, find, i, j);
            }
        }

        return !find.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(new LC79WordSearch().exist(new char[][]{{'a', 'a'}}, "aaa"));
    }
}
